Search Results

Documents authored by Jerrum, Mark

Found 2 Possible Name Variants:

Jerrum, Mark R.

Document
DOI: 10.4230/DagRep.12.11.124
Counting and Sampling: Algorithms and Complexity (Dagstuhl Seminar 22482)

Authors: Holger Dell, Mark R. Jerrum, Haiko Müller, Konrad Anand, and Marcus Pappik

Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22482 "Counting and Sampling: Algorithms and Complexity". We document the talks presented, covering many advances in the area made over the last five years. As well, we document the progress made by working groups on future projects.
Cite as

Holger Dell, Mark R. Jerrum, Haiko Müller, Konrad Anand, and Marcus Pappik. Counting and Sampling: Algorithms and Complexity (Dagstuhl Seminar 22482). In Dagstuhl Reports, Volume 12, Issue 11, pp. 124-145, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{dell_et_al:DagRep.12.11.124,
  author =	{Dell, Holger and Jerrum, Mark R. and M\"{u}ller, Haiko and Anand, Konrad and Pappik, Marcus},
  title =	{{Counting and Sampling: Algorithms and Complexity (Dagstuhl Seminar 22482)}},
  pages =	{124--145},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{11},
  editor =	{Dell, Holger and Jerrum, Mark R. and M\"{u}ller, Haiko and Anand, Konrad and Pappik, Marcus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.11.124},
  URN =		{urn:nbn:de:0030-drops-178394},
  doi =		{10.4230/DagRep.12.11.124},
  annote =	{Keywords: Sampling, Counting, Algorithms, Complexity, Statistical Physics, Phase Transitions, Markov Chains, Graphs, Point Processes}
}
Document
DOI: 10.4230/DagRep.7.8.23
Computational Counting (Dagstuhl Seminar 17341)

Authors: Ivona Bezáková, Leslie Ann Goldberg, and Mark R. Jerrum

Published in: Dagstuhl Reports, Volume 7, Issue 8 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17341 "Computational Counting". The seminar was held from 20th to 25th August 2017, at Schloss Dagstuhl -- Leibnitz Center for Informatics. A total of 43 researchers from all over the world, with interests and expertise in different aspects of computational counting, actively participated in the meeting.
Cite as

Ivona Bezáková, Leslie Ann Goldberg, and Mark R. Jerrum. Computational Counting (Dagstuhl Seminar 17341). In Dagstuhl Reports, Volume 7, Issue 8, pp. 23-44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{bezakova_et_al:DagRep.7.8.23,
  author =	{Bez\'{a}kov\'{a}, Ivona and Goldberg, Leslie Ann and Jerrum, Mark R.},
  title =	{{Computational Counting (Dagstuhl Seminar 17341)}},
  pages =	{23--44},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{8},
  editor =	{Bez\'{a}kov\'{a}, Ivona and Goldberg, Leslie Ann and Jerrum, Mark R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.8.23},
  URN =		{urn:nbn:de:0030-drops-84283},
  doi =		{10.4230/DagRep.7.8.23},
  annote =	{Keywords: approximation algorithms, computational complexity, counting problems, partition functions, phase transitions}
}

Jerrum, Mark

Document
DOI: 10.4230/LIPIcs.ICALP.2018.68
A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability

Authors: Heng Guo and Mark Jerrum

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal network reliability problem, which is to determine the probability that, in a undirected graph, assuming each edge fails independently, the remaining graph is still connected. Our main contribution is to confirm a conjecture by Gorodezky and Pak (Random Struct. Algorithms, 2014), that the expected running time of the "cluster-popping" algorithm in bi-directed graphs is bounded by a polynomial in the size of the input.
Cite as

Heng Guo and Mark Jerrum. A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 68:1-68:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.ICALP.2018.68,
  author =	{Guo, Heng and Jerrum, Mark},
  title =	{{A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{68:1--68:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.68},
  URN =		{urn:nbn:de:0030-drops-90727},
  doi =		{10.4230/LIPIcs.ICALP.2018.68},
  annote =	{Keywords: Approximate counting, Network Reliability, Sampling, Markov chains}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.69
Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling

Authors: Heng Guo and Mark Jerrum

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We present a perfect simulation of the hard disks model via the partial rejection sampling method. Provided the density of disks is not too high, the method produces exact samples in O(log n) rounds, where n is the expected number of disks. The method extends easily to the hard spheres model in d>2 dimensions. In order to apply the partial rejection method to this continuous setting, we provide an alternative perspective of its correctness and run-time analysis that is valid for general state spaces.
Cite as

Heng Guo and Mark Jerrum. Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 69:1-69:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.ICALP.2018.69,
  author =	{Guo, Heng and Jerrum, Mark},
  title =	{{Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{69:1--69:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.69},
  URN =		{urn:nbn:de:0030-drops-90739},
  doi =		{10.4230/LIPIcs.ICALP.2018.69},
  annote =	{Keywords: Hard disks model, Sampling, Markov chains}
}
Document
DOI: 10.4230/DFU.Vol7.15301.205
Counting Constraint Satisfaction Problems

Authors: Mark Jerrum

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)

Abstract
This chapter surveys counting Constraint Satisfaction Problems (counting CSPs, or #CSPs) and their computational complexity. It aims to provide an introduction to the main concepts and techniques, and present a representative selection of results and open problems. It does not cover holants, which are the subject of a separate chapter.
Cite as

Mark Jerrum. Counting Constraint Satisfaction Problems. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 205-231, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InCollection{jerrum:DFU.Vol7.15301.205,
  author =	{Jerrum, Mark},
  title =	{{Counting Constraint Satisfaction Problems}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{205--231},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.205},
  URN =		{urn:nbn:de:0030-drops-69655},
  doi =		{10.4230/DFU.Vol7.15301.205},
  annote =	{Keywords: Approximation algorithms, Computational complexity, Constraint satisfaction problems, Counting problems, Partition functions}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.46
A Complexity Trichotomy for Approximately Counting List H-Colourings

Authors: Andreas Galanis, Leslie Ann Goldberg, and Mark Jerrum

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We examine the computational complexity of approximately counting the list H-colourings of a graph. We discover a natural graph-theoretic trichotomy based on the structure of the graph H. If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is trivially in polynomial time. Otherwise, if H is an irreflexive bipartite permutation graph or a reflexive proper interval graph then approximately counting list H-colourings is equivalent to #BIS, the problem of approximately counting independent sets in a bipartite graph. This is a well-studied problem which is believed to be of intermediate complexity - it is believed that it does not have an FPRAS, but that it is not as difficult as approximating the most difficult counting problems in #P. For every other graph H, approximately counting list H-colourings is complete for #P with respect to approximation-preserving reductions (so there is no FPRAS unless NP = RP). Two pleasing features of the trichotomy are (i) it has a natural formulation in terms of hereditary graph classes, and (ii) the proof is largely self-contained and does not require any universal algebra (unlike similar dichotomies in the weighted case). We are able to extend the hardness results to the bounded-degree setting, showing that all hardness results apply to input graphs with maximum degree at most 6.
Cite as

Andreas Galanis, Leslie Ann Goldberg, and Mark Jerrum. A Complexity Trichotomy for Approximately Counting List H-Colourings. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{galanis_et_al:LIPIcs.ICALP.2016.46,
  author =	{Galanis, Andreas and Goldberg, Leslie Ann and Jerrum, Mark},
  title =	{{A Complexity Trichotomy for Approximately Counting List H-Colourings}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{46:1--46:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.46},
  URN =		{urn:nbn:de:0030-drops-63262},
  doi =		{10.4230/LIPIcs.ICALP.2016.46},
  annote =	{Keywords: approximate counting, graph homomorphisms, list colourings}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.582
#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region

Authors: Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, and Eric Vigoda

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an FPRAS nor is as hard as #SAT to approximate. We study #BIS in the general framework of two-state spin systems in bipartite graphs. Such a system is parameterized by three numbers (beta,gamma,lambda), where beta (respectively gamma) represents the weight of an edge (or "interaction strength") whose endpoints are of the same 0 (respectively 1) spin, and lambda is the weight of a 1 vertex, also known as an "external field". By convention, the edge weight with unequal 0/1 end points and the vertex weight with spin 0 are both normalized to 1. The partition function of the special case beta=1, gamma=0, and lambda=1 counts the number of independent sets. We define two notions, nearly-independent phase-correlated spins and symmetry breaking. We prove that it is #BIS-hard to approximate the partition function of any two-spin system on bipartite graphs supporting these two notions. As a consequence, we show that #BIS on graphs of degree at most 6 is as hard to approximate as #BIS~without degree bound. The degree bound 6 is the best possible as Weitz presented an FPTAS to count independent sets on graphs of maximum degree 5. This result extends to the hard-core model and to other anti-ferromagnetic two-spin models. In particular, for all antiferromagnetic two-spin systems, namely those satisfying beta*gamma<1, we prove that when the infinite (Delta-1)-ary tree lies in the non-uniqueness region then it is #BIS-hard to approximate the partition function on bipartite graphs of maximum degree Delta, except for the case beta=gamma and lambda=1. The exceptional case is precisely the antiferromagnetic Ising model without an external field, and we show that it has an FPRAS on bipartite graphs. Our inapproximability results match the approximability results of Li et al., who presented an FPTAS for general graphs of maximum degree Delta when the parameters lie in the uniqueness region.
Cite as

Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, and Eric Vigoda. #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 582-595, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.APPROX-RANDOM.2014.582,
  author =	{Cai, Jin-Yi and Galanis, Andreas and Goldberg, Leslie Ann and Guo, Heng and Jerrum, Mark and Stefankovic, Daniel and Vigoda, Eric},
  title =	{{#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{582--595},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.582},
  URN =		{urn:nbn:de:0030-drops-47235},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.582},
  annote =	{Keywords: Spin systems, approximate counting, complexity, #BIS-hardness, phase transition}
}
Document
DOI: 10.4230/DagRep.3.1.47
Computational Counting (Dagstuhl Seminar 13031)

Authors: Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum, and Pascal Koiran

Published in: Dagstuhl Reports, Volume 3, Issue 1 (2013)

Abstract
Dagstuhl Seminar 13031 "Computational Counting" was held from 13th to 18th January 2013, at Schloss Dagstuhl -- Leibnitz Center for Informatics. A total of 43 researchers from all over the world, with interests and expertise in different aspects of computational counting, actively participated in the meeting.
Cite as

Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum, and Pascal Koiran. Computational Counting (Dagstuhl Seminar 13031). In Dagstuhl Reports, Volume 3, Issue 1, pp. 47-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{burgisser_et_al:DagRep.3.1.47,
  author =	{B\"{u}rgisser, Peter and Goldberg, Leslie Ann and Jerrum, Mark and Koiran, Pascal},
  title =	{{Computational Counting (Dagstuhl Seminar 13031)}},
  pages =	{47--66},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{1},
  editor =	{B\"{u}rgisser, Peter and Goldberg, Leslie Ann and Jerrum, Mark and Koiran, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.1.47},
  URN =		{urn:nbn:de:0030-drops-40087},
  doi =		{10.4230/DagRep.3.1.47},
  annote =	{Keywords: Computational complexity, counting problems, graph polynomials, holographic algorithms, statistical physics, constraint satisfaction}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.148
The complexity of approximating conservative counting CSPs

Authors: Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, and David Richerby

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We study the complexity of approximation for a weighted counting constraint satisfaction problem #CSP(F). In the conservative case, where F contains all unary functions, a classification is known for the Boolean domain. We give a classification for problems with general finite domain. We define weak log-modularity and weak log-supermodularity, and show that #CSP(F) is in FP if F is weakly log-modular. Otherwise, it is at least as hard to approximate as #BIS, counting independent sets in bipartite graphs, which is believed to be intractable. We further sub-divide the #BIS-hard case. If F is weakly log-supermodular, we show that #CSP(F) is as easy as Boolean log-supermodular weighted #CSP. Otherwise, it is NP-hard to approximate. Finally, we give a trichotomy for the arity-2 case. Then, #CSP(F) is in FP, is #BIS-equivalent, or is equivalent to #SAT, the problem of approximately counting satisfying assignments of a CNF Boolean formula.
Cite as

Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, and David Richerby. The complexity of approximating conservative counting CSPs. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 148-159, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.STACS.2013.148,
  author =	{Chen, Xi and Dyer, Martin and Goldberg, Leslie Ann and Jerrum, Mark and Lu, Pinyan and McQuillan, Colin and Richerby, David},
  title =	{{The complexity of approximating conservative counting CSPs}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{148--159},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.148},
  URN =		{urn:nbn:de:0030-drops-39303},
  doi =		{10.4230/LIPIcs.STACS.2013.148},
  annote =	{Keywords: counting constraint satisfaction problem, approximation, complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.302
Log-supermodular functions, functional clones and counting CSPs

Authors: Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
Motivated by a desire to understand the computational complexity of counting constraint satisfaction problems (counting CSPs), particularly the complexity of approximation, we study functional clones of functions on the Boolean domain, which are analogous to the familiar relational clones constituting Post's lattice. One of these clones is the collection of log-supermodular (lsm) functions, which turns out to play a significant role in classifying counting CSPs. In our study, we assume that non-negative unary functions (weights) are available. Given this, we prove that there are no functional clones lying strictly between the clone of lsm functions and the total clone (containing all functions). Thus, any counting CSP that contains a single nontrivial non-lsm function is computationally as hard as any problem in #P. Furthermore, any non-trivial functional clone (in a sense that will be made precise below) contains the binary function "implies". As a consequence, all non-trivial counting CSPs (with non-negative unary weights assumed to be available) are computationally at least as difficult as #BIS, the problem of counting independent sets in a bipartite graph. There is empirical evidence that #BIS is hard to solve, even approximately.
Cite as

Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Log-supermodular functions, functional clones and counting CSPs. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 302-313, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.STACS.2012.302,
  author =	{Bulatov, Andrei A. and Dyer, Martin and Goldberg, Leslie Ann and Jerrum, Mark},
  title =	{{Log-supermodular functions, functional clones and counting CSPs}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{302--313},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.302},
  URN =		{urn:nbn:de:0030-drops-34078},
  doi =		{10.4230/LIPIcs.STACS.2012.302},
  annote =	{Keywords: counting constraint satisfaction problems, approximation, complexity}
}
Document
DOI: 10.4230/DagSemProc.10481.1
10481 Abstracts Collection – Computational Counting

Authors: Peter Bürgisser, Leslie Ann Goldberg, and Mark Jerrum

Published in: Dagstuhl Seminar Proceedings, Volume 10481, Computational Counting (2011)

Abstract
From November 28 to December 3 2010, the Dagstuhl Seminar 10481 ``Computational Counting'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Peter Bürgisser, Leslie Ann Goldberg, and Mark Jerrum. 10481 Abstracts Collection – Computational Counting. In Computational Counting. Dagstuhl Seminar Proceedings, Volume 10481, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{burgisser_et_al:DagSemProc.10481.1,
  author =	{B\"{u}rgisser, Peter and Goldberg, Leslie Ann and Jerrum, Mark},
  title =	{{10481 Abstracts Collection – Computational Counting}},
  booktitle =	{Computational Counting},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10481},
  editor =	{Peter B\"{u}rgisser and Leslie Ann Goldberg and Mark Jerrum},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10481.1},
  URN =		{urn:nbn:de:0030-drops-29453},
  doi =		{10.4230/DagSemProc.10481.1},
  annote =	{Keywords: Computational complexity, counting problems, holographic algorithms, statistical physics, constraint satisfaction}
}
Document
DOI: 10.4230/DagSemProc.10481.2
10481 Executive Summary – Computational Counting

Authors: Peter Bürgisser, Leslie Ann Goldberg, and Mark Jerrum

Published in: Dagstuhl Seminar Proceedings, Volume 10481, Computational Counting (2011)

Abstract
From November 28 to December 3 2010, the Dagstuhl seminar 10481 ``Computational Counting'' was held in Schloss Dagstuhl – Leibnitz Center for Informatics. 36 researchers from all over the world, with interests and expertise in different aspects of computational counting, actively participated in the meeting.
Cite as

Peter Bürgisser, Leslie Ann Goldberg, and Mark Jerrum. 10481 Executive Summary – Computational Counting. In Computational Counting. Dagstuhl Seminar Proceedings, Volume 10481, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{burgisser_et_al:DagSemProc.10481.2,
  author =	{B\"{u}rgisser, Peter and Goldberg, Leslie Ann and Jerrum, Mark},
  title =	{{10481 Executive Summary – Computational Counting}},
  booktitle =	{Computational Counting},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10481},
  editor =	{Peter B\"{u}rgisser and Leslie Ann Goldberg and Mark Jerrum},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10481.2},
  URN =		{urn:nbn:de:0030-drops-29441},
  doi =		{10.4230/DagSemProc.10481.2},
  annote =	{Keywords: Computational complexity, counting problems, holographic algorithms, statistical physics, constraint satisfaction}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1821
A Complexity Dichotomy for Partition Functions with Mixed Signs

Authors: Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
\emph{Partition functions}, also known as \emph{homomorphism functions}, form a rich family of graph invariants that contain combinatorial invariants such as the number of $k$-colourings or the number of independent sets of a graph and also the partition functions of certain ``spin glass'' models of statistical physics such as the Ising model. Building on earlier work by Dyer and Greenhill (2000) and Bulatov and Grohe (2005), we completely classify the computational complexity of partition functions. Our main result is a dichotomy theorem stating that every partition function is either computable in polynomial time or \#P-complete. Partition functions are described by symmetric matrices with real entries, and we prove that it is decidable in polynomial time in terms of the matrix whether a given partition function is in polynomial time or \#P-complete. While in general it is very complicated to give an explicit algebraic or combinatorial description of the tractable cases, for partition functions described by a Hadamard matrices --- these turn out to be central in our proofs --- we obtain a simple algebraic tractability criterion, which says that the tractable cases are those ``representable'' by a quadratic polynomial over the field $\ensuremath{\mathbb{F}_2}$.
Cite as

Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A Complexity Dichotomy for Partition Functions with Mixed Signs. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 493-504, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.STACS.2009.1821,
  author =	{Goldberg, Leslie Ann and Grohe, Martin and Jerrum, Mark and Thurley, Marc},
  title =	{{A Complexity Dichotomy for Partition Functions with Mixed Signs}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{493--504},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1821},
  URN =		{urn:nbn:de:0030-drops-18217},
  doi =		{10.4230/LIPIcs.STACS.2009.1821},
  annote =	{Keywords: Computational complexity}
}
Document
DOI: 10.4230/DagSemProc.08201.1
08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms

Authors: Martin E. Dyer, Mark Jerrum, and Marek Karpinski

Published in: Dagstuhl Seminar Proceedings, Volume 8201, Design and Analysis of Randomized and Approximation Algorithms (2008)

Abstract
From 11.05.08 to 16.05.08, the Dagstuhl Seminar 08201 ``Design and Analysis of Randomized and Approximation Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research work, and ongoing work and open problems were discussed. Abstracts of the presentations which were given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full paper are provided, if available.
Cite as

Martin E. Dyer, Mark Jerrum, and Marek Karpinski. 08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms. In Design and Analysis of Randomized and Approximation Algorithms. Dagstuhl Seminar Proceedings, Volume 8201, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{dyer_et_al:DagSemProc.08201.1,
  author =	{Dyer, Martin E. and Jerrum, Mark and Karpinski, Marek},
  title =	{{08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms}},
  booktitle =	{Design and Analysis of Randomized and Approximation Algorithms},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8201},
  editor =	{Martin E. Dyer and Mark Jerrum and Marek Karpinski},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08201.1},
  URN =		{urn:nbn:de:0030-drops-15518},
  doi =		{10.4230/DagSemProc.08201.1},
  annote =	{Keywords: Randomized Algorithms, Approximation Algorithms, Optimization Problems, Measurement Problems, Approximation Complexity, Algorithmic Game Theory, Internet, Decentralized Networks, Network Design}
}
Document
DOI: 10.4230/DagSemProc.05201.1
05201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms

Authors: Martin Dyer, Mark Jerrum, and Marek Karpinski

Published in: Dagstuhl Seminar Proceedings, Volume 5201, Design and Analysis of Randomized and Approximation Algorithms (2005)

Abstract
From 15.05.05 to 20.05.05, the Dagstuhl Seminar 05201 ``Design and Analysis of Randomized and Approximation Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Martin Dyer, Mark Jerrum, and Marek Karpinski. 05201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms. In Design and Analysis of Randomized and Approximation Algorithms. Dagstuhl Seminar Proceedings, Volume 5201, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{dyer_et_al:DagSemProc.05201.1,
  author =	{Dyer, Martin and Jerrum, Mark and Karpinski, Marek},
  title =	{{05201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms}},
  booktitle =	{Design and Analysis of Randomized and Approximation Algorithms},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5201},
  editor =	{Martin Dyer and Mark Jerrum and Marek Karpinski},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05201.1},
  URN =		{urn:nbn:de:0030-drops-3191},
  doi =		{10.4230/DagSemProc.05201.1},
  annote =	{Keywords: Randomized Algorithms, Approximation Algorithms, Optimization Problems, Measurement Problems, Decentralized Networks}
}
Document
DOI: 10.4230/DagSemRep.309
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 01231)

Authors: Martin Dyer, Mark Jerrum, and Marek Karpinski

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Martin Dyer, Mark Jerrum, and Marek Karpinski. Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 01231). Dagstuhl Seminar Report 309, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{dyer_et_al:DagSemRep.309,
  author =	{Dyer, Martin and Jerrum, Mark and Karpinski, Marek},
  title =	{{Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 01231)}},
  pages =	{1--28},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{309},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.309},
  URN =		{urn:nbn:de:0030-drops-151930},
  doi =		{10.4230/DagSemRep.309},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact